package com.zhaofan.interview;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/lru-cache-lcci/
 */
public class No1625 {
    private final Integer DEFAULT_CAPACITY = 16;

    private Map<Integer, Integer> cache;
    private int capacity;
    private Info[] infos;
    private int length = 0;


    public No1625(Integer capacity) {
        this.capacity = capacity;
        infos = new Info[capacity];
        this.cache = new HashMap<>(capacity);
    }

    public No1625() {
        this.capacity = DEFAULT_CAPACITY;
        this.infos = new Info[this.capacity];
        cache = new HashMap<>(DEFAULT_CAPACITY);
    }

    public int get(int key) {
        Integer result = cache.get(key);
        if (result == null) {
            return -1;
        } else {
            Info info = infos[result];
            rightShift(result);
            cache.put(key, 0);
            infos[0] = info;

            return info.value;
        }
    }

    public void put(int key, int value) {
        Integer v = cache.get(key);
        if (v != null) {
            Info info = infos[cache.get(key)];
            rightShift(v);
            cache.put(key, 0);
            info.value = value;
            infos[0] = info;
        } else {
            if (isFull()) {
                cache.remove(infos[capacity - 1].key);
                rightShift(length - 1);
                length--;
            } else {
                rightShift(length);
            }
            cache.put(key, 0);
            infos[0] = new Info(key, value);
            length++;
        }
    }

    public boolean isFull() {
        return length == capacity;
    }

    //將第end位之前的元素向后移動一位
    public void rightShift(int end) {
        for (int i = end - 1; i >= 0; i--) {
            infos[i + 1] = infos[i];
            Info info = infos[i + 1];
            Integer key = info.key;
            cache.put(key, i + 1);
        }

    }

    public class Info {
        public Integer key;
        public Integer value;

        public Info(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
        No1625 cache = new No1625(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));       // 返回  1
        cache.put(3, 3);    // 该操作会使得密钥 2 作废
        System.out.println(cache.get(2));       // 返回 -1 (未找到)
        cache.put(4, 4);    // 该操作会使得密钥 1 作废
        System.out.println(cache.get(1));       // 返回 -1 (未找到)
        System.out.println(cache.get(3));       // 返回  3
        System.out.println(cache.get(4));       // 返回  4
    }

}

